package niuke;

import java.util.HashMap;
import java.util.Map;

/**
 * @author wangmaolin1
 * @date 2022/7/30 10:52 上午
 */
public class _93LRU2 {

    private int capacity;
    private Map<Integer, Node> map;
    private Node head;
    private Node tail;

    private int size;


    public _93LRU2(int capacity) {
        // write code here
        this.capacity = capacity;
        this.map = new HashMap<>(capacity);
    }



    public int get(int key) {
        // write code here
        if (map.containsKey(key)) {
            //get的node移到head
            Node node = map.get(key);
            this.move2Head(node);
            return node.value;
        }

        return -1;
    }

    public void set(int key, int value) {
        // write code here
        Node val;
        if (map.containsKey(key)) {
            //todo 修改node值，并移到haed
            val = map.get(key);
            val.value = value;
            this.move2Head(val);

        } else {
            //todo 放到head
            if (head == null) {
                // head为空，初始化
                head = new Node(key, value);
                tail = head;
                val = head;
                size++;
            } else {
                // 当前节点直接放到head节点
                val = new Node(key, value, null, head);
                head.pre = val;
                head = val;
                size++;
            }
        }
        if (size > capacity) {
            // 超过总cap，移除末尾的
            this.removeTail();
        }

        // 更新原始map
        map.put(key, val);
    }

    private void removeTail() {
        if (tail != null) {
            // map值移除
            map.remove(tail.key);
            tail.pre.next = null;
            tail = tail.pre;
        }
    }

    private void move2Head(Node node) {

        if (this.head.equals(node)) {
            return;
        }
        if (this.tail.equals(node)) {
            this.tail.pre.next=null;
            this.tail= this.tail.pre;
            node.next = head;
            head.pre=node;
            node.pre = null;
            head = node;
            return;
        }
        if (node.pre != null) {
            node.pre.next = node.next;
        }
        if (node.next != null) {
            node.next.pre = node.pre;
        }
        node.next = head;
        head.pre = node;
        head = node;
    }

    public static class Node {
        private int key;
        private int value;
        private Node pre;
        private Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }

        public Node(int key, int value, Node pre, Node next) {
            this.key = key;
            this.value = value;
            this.pre = pre;
            this.next = next;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", value=" + value +
                    '}';
        }
    }

    @Override
    public String toString() {
        return "_93LRU2{" +
                ", map=" + map +
                ", size=" + size +
                '}';
    }

    public static void main(String[] args) {
        _93LRU2 map = new _93LRU2(3);
        map.set(1, 1);
        map.set(2, 2);
        map.set(3, 3);
        map.set(4,4);
        map.set(5,5);
        System.out.println(map);
        System.out.println(map.get(3));
        System.out.println(map);
    }

}
